/*
 * @lc app=leetcode.cn id=102 lang=golang
 *
 * [102] 二叉树的层序遍历
 */

// 2. 循环
// @lc code=start
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func levelOrder(root *TreeNode) (ans [][]int) {
	nodes := []*TreeNode{root}
	for len(nodes) > 0 {
		var temp []int
		var nextLevel []*TreeNode
		for i := 0; i < len(nodes); i++ {
			if nodes[i] != nil {
				temp = append(temp, nodes[i].Val)
				nextLevel = append(nextLevel, nodes[i].Left)
				nextLevel = append(nextLevel, nodes[i].Right)
			}
		}
		if temp != nil {
			ans = append(ans, temp)
		}
		nodes = nextLevel
	}
	return
}

// @lc code=end

// 1. 递归
// @lc code=start
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func levelOrder(root *TreeNode) (ans [][]int) {
	var level func(nodes []*TreeNode)
	level = func(nodes []*TreeNode) {
		if len(nodes) == 0 {
			return
		}
		temp := []int{}
		nextLevel := []*TreeNode{}
		for _, node := range nodes {
			if node != nil {
				temp = append(temp, node.Val)
				nextLevel = append(nextLevel, node.Left)
				nextLevel = append(nextLevel, node.Right)
			}
		}
		if len(temp) > 0 {
			ans = append(ans, temp)
		}
		level(nextLevel)
	}

	level([]*TreeNode{root})
	return
}

// @lc code=end

